\section{Analysis of maximin support}\label{s:complexity}

Consider a multiwinner election instance $(G=(N\cup C, E), s, k)$ as defined in Section~\ref{s:prel}. 
In this section we present a computational complexity analysis of the maximin support problem, including new results both on approximability and on hardness. 

We start by establishing that our security objective \eqref{eq:security} is indeed equivalent to maximin support.
The proof of the next theorem is delayed to Appendix~\ref{s:proofs}.

\begin{theorem} \label{thm:equivalence} 
For a fixed committee $A$, 
$$\max_{\text{feasible } w} \ \supp_w(A) = \min_{A' \subseteq A, \ A'\neq \emptyset} \ \frac{1}{|A'|} \sum_{n\in \cup_{c\in A'} N_c} s_n.$$
Hence maximin support, the problem of maximizing the left-hand side over all full committees $A$,  
is equivalent to that of maximizing the right-hand side over all full committees $A$. 
Furthermore, this equivalence preserves approximations, as any committee provides the same objective value to both problems.
\end{theorem}

Next, we compare how some of the most relevant efficient election rules perform in terms of security, and highlight the effectiveness of the maximin support objective for preventing overrepresentation. 
Fix a committee size $k$ and consider an unweighted instance with $k+1$ voters and $2k$ candidates. 
For $1\leq i\leq k$, voter $n_i$ supports the candidate set $\{c_1, \cdots, c_i\}$, and the last voter $n'$ supports the candidate set $\{c_1', \cdots, c_k'\}$. See Figure~\ref{fig:example}.
%
We assume that an adversary controls the last voter and the last $k$ candidates, and will use any elected representatives to attempt to disrupt the duties of the committee. 
How many representatives will it get? 

\begin{figure}[htb]
  \centering
	\includegraphics[width={0.45\linewidth},natwidth=180,natheight=220]{figure-example.pdf}
  \caption{In this example, the last voter and the last $k$ candidates are considered adversarial.}
  \label{fig:example}
\end{figure}

\begin{lemma}\label{lem:badexamples}
For any $\alpha \geq 1$, in the example above the number of adversarial candidates elected by a rule with an $\alpha$-approximation guarantee for maximin support is at most $\lfloor \alpha \rfloor$. 
On the other hand, this number is $\Omega(\sqrt{k})$ for proportional approval voting (PAV), and $\Omega(\log k)$ for both $\phragmen$ and Rule X. 
Hence, none of these three rules guarantees a constant-factor approximation. 
\end{lemma}

The proof is delayed to Appendix~\ref{s:proofs}. 
For definitions of these rules, we direct the reader to the survey paper~\cite{lackner2020approval}.
We only remark here that Rule X~\cite{peters2019proportionality} is a recently proposed rule inspired in $\phragmen$ -- much as our own rule presented in the next section -- that achieves the EJR property. 

The maximin support problem was introduced in~\cite{sanchez2016maximin}, where it was observed to be NP-hard. We show now a stronger hardness result for it, which in particular rules out the existence of a PTAS.%
\footnote{A \emph{polynomial time approximation scheme} (PTAS) for an optimization problem is an algorithm that, for any constant $\eps>0$ and any given instance, returns a $(1+\eps)$-factor approximation in polynomial time.} 


\begin{theorem}
For any constant $\eps>0$, it is NP-hard to approximate the unweighted maximin support problem within a factor $\alpha=1.2-\eps$.
\end{theorem}

\begin{figure}[htb]
  \centering
	\includegraphics[width=\linewidth,natwidth=400,natheight=185]{figure-hardness.pdf}
  \caption{Reducing an instance of the $k$-independent set problem on cubic graphs to one of the maximin support problem. Set $N$ is represented by triangles and $C$ by circles.}
  \label{fig:hardness}
\end{figure}

\begin{proof}
We present a reduction from the $k$-independent set problem on cubic graphs, which is known to be NP-hard~\cite{johnson1979computers}. In this problem, one is given a graph $G'=(V',E')$ where every vertex has degree exactly 3, and a parameter $k'$, and one must decide whether there is a vertex subset $I\subseteq V'$ of size $k'$ such that no two vertices in $I$ are adjacent, i.e., $I$ is an independent set. 
Given such an instance, we define an instance $(G=(N\cup C, E), s, k)$ of maximin support where $k=k'$, $C=V'$ (each vertex in $V'$ corresponds to a candidate), and $N=E'$ with $s_n=1$ and $C_n=n$ for each $n\in N$ (each edge in $E'$ corresponds to a voter with unit vote that approves of the two candidates on its endpoints); see Figure~\ref{fig:hardness}.
Notice that in this instance, each candidate is approved by exactly 3 voters, and two candidates $c, c'$ have an approving voter in common if and only if $c$ and $c'$ are adjacent in $V'$.

Hence, if there is an independent set $I$ of size $k$ in $G'$, the same committee of validators in $G$ can be assigned the full vote of each of its three approving voters, so that each receives a support of 3 units, which is clearly maximal. On the other hand, if there is no independent set of size $k$ in $G'$, then for any solution $(A,w)$ of the maximin support instance there must be two committee members $c,c'\in A$ who have an approving voter in common. These two members have at most five voters approving either of them, so one of them must have a support of at most $5/2$. This shows that $\supp_w(A)\leq 5/2$ for any feasible solution $(A,w)$. Finally, the ratio between the objective values $3$ and $5/2$ is $6/5=1.2>\alpha$, so the assumed $\alpha$-approximation algorithm for maximin support would allow us to distinguish between these two cases and decide whether such an independent set $I$ exists. This completes the proof.
\end{proof}


In contrast, we show that the recently proposed $\MMS$ rule~\cite{sanchez2016maximin}, known to achieve the PJR property, also provides a 2-approximation for maximin support. 
In simple terms, $\MMS$ (Algorithm~\ref{alg:mms}) starts with an empty committee $A$ and iteratively adds candidates to it; in each iteration, it computes a balanced weight vector for each possible augmented committee that can be obtained by adding a candidate, and then inserts the candidate whose corresponding augmented committee has the highest least member support.
%
We will need the following key technical result, whose proof uses the flow decomposition theorem and is delayed to Appendix~\ref{s:flow}. 

\begin{algorithm}[htb]
\SetAlgoLined
\KwData{Bipartite approval graph $G=(N\cup C, E)$, vector $s$ of vote strengths, target committee size $k$.}
Initialize $A=\emptyset$\ and $w=0\in \R^E$\;
\For{$i$ from $1$ to $k$}{
	\For{each candidate $c\in C\setminus A$}{
		Compute a balanced\footnotemark ~weight vector $w_c$ for $A+c$\;
		}
Find $c_i\in \arg\max_{c\in C\setminus A} \supp_{w_c}(A+c)$\;
Update $A\leftarrow A+c_i$ and $w\leftarrow w_{c_i}$\;
}
\Return $(A,w)$\;
\caption{$\MMS$, proposed in~\cite{sanchez2016maximin}}
\label{alg:mms}
\end{algorithm}
\footnotetext{The original algorithm in~\cite{sanchez2016maximin} does not compute a balanced weight vector, but any vector $w$ that maximizes $\supp_w(A)$, which is sufficient for our analysis. 
We consider balanced vectors here for ease of comparison with other algorithms in the paper and because this requirement does not seem to cause any increase in complexity.}

\begin{lemma}\label{lem:2sols}
If $(A^*, w^*)$ is an optimal solution to maximin support, and $(A,w)$ is a partial solution with $|A|\leq k$ and $A\neq A^*$, there is a candidate $c'\in A^*\setminus A$ and feasible solution $(A+c', w')$ such that 
$$\supp_{w'}(A+c')\geq \min\Big\{\supp_w(A), \frac{1}{2} \supp_{w^*}(A^*)\Big\}.$$
\end{lemma}

\begin{theorem}\label{thm:mms}
The $\MMS$ rule provides a 2-approximation for maximin support.
\end{theorem}

\begin{proof}
Let $(A_i, w_i)$ be the partial solution at the end of the $i$-th round of MMS, and let $(A^*, w^*)$ be an optimal solution. 
We prove by induction on $i$ that $\supp_{w_i}(A_i)\geq \frac{1}{2}\supp_{w^*}(A^*)$, where the case $i=0$ holds trivially as we use the convention that $\supp_w(\emptyset)=\infty$.
Assuming that the inequality holds for $i$, an application of Lemma~\ref{lem:2sols} for $(A_i, w_i)$ and $(A^*, w^*)$ implies that there is a candidate $c'\in A^*\setminus A_i$ and a feasible solution $(A_i+c', w')$ such that 
\begin{align*}
\supp_{w'}(A_i+c') &\geq \min\Big\{\supp_{w_i}(A_i), \frac{1}{2} \supp_{w^*}(A^*)\Big\} \\
 &= \frac{1}{2} \supp_{w^*}(A^*).
\end{align*}
%
As the algorithm is bound to inspect candidate $c'$ in round $i+1$, and compute for it a balanced weight vector $w_{c'}$ which maximizes the support of $A_i+c'$ (by Lemma~\ref{lem:balanced}), the solution $(A_{i+1}, w_{r+1})$ at the end of round $i+1$ must have an even higher support, i.e., %
\begin{align*}
\supp_{w_{i+1}}(A_{i+1}) &\geq \supp_{w_{c'}}(A_i+c) \\ 
  &\geq \supp_{w'}(A_i+c) \geq \frac{1}{2} \supp_{w^*}(A^*).
\end{align*}
%
This completes the proof.
\end{proof}

$\MMS$ is an greedy algorithm with a runtime of $O(\bal \cdot |C|\cdot k)$, where we recall that $\bal$ is the time complexity of computing a balanced weight vector; see Remark~\ref{rem:bal}. 
To conclude the section we mention that a "lazy greedy" version of it can save a factor $\Theta(k)$ in the runtime while keeping the approximation guarantee virtually unchanged. 
In Appendix~\ref{s:lazymms} we prove the following result.

\begin{theorem}\label{thm:2eps}
There is an algorithm $\lazy$ that, for any $\eps>0$, offers a $(2+\eps)$-approximation for the maximin support problem, satisfies the PJR property, and executes in time $O(\bal\cdot |C|\cdot \log(1/\eps))$.
\end{theorem}

